//压缩增量包
function MinChunk(chunkArr,s1) {
  var minChunk=[]
  for(let i=0;i<chunkArr.length;i++){
    let arr=chunkArr[i];
    if(arr[0]==='e'&&arr[2]<String(arr[1]).length+String(arr[2]).length){
      arr=['a',s1.substr(arr[1],arr[2])]
    }
    var lastArr=minChunk[minChunk.length-1];
    if(arr[0]==='a'&&lastArr&&lastArr[0]==='a'){
      lastArr[1]=lastArr[1]+arr[1];
    }else{
      minChunk.push(arr)
    }
  }
  const narr=[]
  for(let i=0;i<minChunk.length;i++){
    let arr=minChunk[i];
    if(arr[0]==='a'){
      narr.push(arr[1])
    }else if(arr[0]==='e'){
      narr.push([arr[1],arr[2]])
    }
  }
  return narr;
}

//比较两字符的相等长度和大小
function compareLen(n1,n2,str1,str2) {
  //求出相等部分
  var len=0;
  while (n1+len<=str1.length&&n2+len<=str2.length&&str1.charCodeAt(n1+len)===str2.charCodeAt(n2+len)){
    len++;
  }
  var code1=str1.charCodeAt(n1+len);
  var code2=str2.charCodeAt(n2+len);

  if(Number.isNaN(code1)&&Number.isNaN(code2)){
    return [len,0]
  }else if(Number.isNaN(code1)){
    return [len,-1]
  }else if(Number.isNaN(code2)){
    return [len,1]
  }else{
    //求出大小
    var dis=0;
    if(code1<code2){
      dis=-1
    }else if(code1>code2){
      dis=1
    }
    if(str1.substr(n1,len)!==str2.substr(n2,len)){
      console.log(dis,len,str1.substr(n1,len),'===',str2.substr(n2,len),n1,n2,str1.length,str2.length)
    }

    return [len,dis];
  }
}

//查找字符在数组的最大相等长度和大小
function findLen(str,hasSortArr,callback) {
  var l=0,r=hasSortArr.length;
  var lock=-1;
  var len1=0,len2=0;
  var len=0,dis=0;

  if(hasSortArr.length>0){
    [len1,dis]=callback(str,hasSortArr[0]);
    if(dis<1){
      return [0,len1,dis]
    }
    [len2,dis]=callback(str,hasSortArr[r-1]);
    if(dis>-1){
      return [r-1,len2,dis]
    }
    while(lock===-1){
      var m=(l+r+1)>>1;
      //比较下坐标大小
      [len,dis]=callback(str,hasSortArr[m])
      if(dis===1){
        if(m+1===r){
          if(len<len2){
            lock=r;
            len=len2;
            dis=-1
          }else{
            lock=m;
          }
        }else{
          len1=len;
          l=m
        }
      }else if(dis===-1){
        if(l+1===m){
          if(len<len1){
            lock=l;
            len=len1;
            dis=1
          }else{
            lock=m;
          }
        }else{
          len2=len;
          r=m
        }
      }else{
        lock=m;
      }
    }
    return [lock,len,dis]
  }
  return [lock,0,1]
}

//SA[i]表示排名为i的后缀下标、rk[i]表示起始位置的下标为i的后缀的排名
function getSa(str) {
  var sLen=str.length;//总共排名长度
  //后缀数组
  var sa=[];
  for(var i=0;i<sLen;i++){
    var [n,len,dis]=findLen(i,sa,function (n1,n2) {
      return compareLen(n1,n2,str,str)
    })
    if(dis===1){
      sa.splice(n+1,0,i)
    }else{
      sa.splice(n,0,i)
    }

  }
  return sa
}
//用后缀数组，求两个字符的公共子串,也就是两个文件的公共部分
function makeChunk(s1,s2){
  var sa1=getSa(s1);//后缀数组，排序
  const chunkArr=[]
  let i=0;
  while (i<s2.length){
    var [n,len,dis]=findLen(i,sa1,function (n2,n1) {
      return compareLen(n2,n1,s2,s1)
    })
    if(len>0){
      chunkArr.push(['e',sa1[n],len])
      i=i+len;
    }else{
      chunkArr.push(['a',s2[i]])
      i++
    }
  }
  return chunkArr;
}
//执行增量包
function execChunk(s1,chunk){
  var ns='';
  for(var i=0;i<chunk.length;i++){
    var arr=chunk[i];
    if(Object.prototype.toString.call(arr)==='[object Array]'){
      ns=ns+s1.substr(arr[0],arr[1])
    }else{
      ns=ns+arr
    }
  }
  return ns;
}
module.exports=function (s1,s2) {
  const chunk=makeChunk(s1,s2);

  const chunkArr=MinChunk(chunk,s1)
  const s3=execChunk(s1,chunkArr)
  if(s3!==s2){
    throw '增量包打包错误'
  }
  return chunkArr
};
